package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/check-if-a-string-is-a-valid-sequence-from-root-to-leaves-path-in-a-binary-tree'>判断给定的序列是否是二叉树从根到叶的路径(Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree)</a>
 * <p>给定一个二叉树，我们称从根节点到任意叶节点的任意路径中的节点值所构成的序列为该二叉树的一个 “有效序列” 。检查一个给定的序列是否是给定二叉树的一个 “有效序列” 。</p>
 * <p>我们以整数数组 arr 的形式给出这个序列。从根节点到任意叶节点的任意路径中的节点值所构成的序列都是这个二叉树的 “有效序列” 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
 *                              <font color='green'>0</font>
 *                           /     \
 *                          <font color='green'>1</font>       0
 *                        /   \    /
 *                       <font color='green'>0</font>     1  0
 *                        \   / \
 *                         <font color='green'>1</font> 0   0
 *      输出：true
 *      解释：
 *          路径 0 -> 1 -> 0 -> 1 是一个“有效序列”（图中的绿色节点）。
 *          其他的“有效序列”是：
 *              0 -> 1 -> 1 -> 0
 *              0 -> 0 -> 0
 *  示例 2：
 *      输入：root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
 *      输出：false
 *      解释：路径 0 -> 0 -> 1 不存在，所以这不是一个“序列”。
 *
 *  示例 3：
 *      输入：root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
 *      输出：false
 *      解释：路径 0 -> 1 -> 1 是一个序列，但不是一个“有效序列”（译者注：因为序列的终点不是叶节点）。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= arr.length <= 5000</li>
 *     <li>0 <= arr[i] <= 9</li>
 *     <li>每个节点的值的取值范围是 [0 - 9]</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/20 10:14
 */
public class LC1430IsValidSequence_M {
    public boolean isValidSequence(TreeNode root, int[] arr) {
        return dfs(root, 0, arr);
    }

    private boolean dfs(TreeNode currNode, int idx, int[] arr) {
        if (currNode == null || currNode.val != arr[idx]) {
            return false;
        }
        if (idx == arr.length - 1) {
            return currNode.left == currNode.right;
        }
        return dfs(currNode.left, idx + 1, arr) || dfs(currNode.right, idx + 1, arr);
    }
}
